package FourthWeek;

public class Sunday {
    //441、排列硬币
    public int arrangeCoins(int n) {
        int left = 1,right = n;
        while(left < right) {
            //可以根据等差数列的公式：n = mid * (mid + 1) / 2 -> mid * (mid + 1) = 2 * n
            int mid = left + (right - left + 1) / 2;
            if ((long) mid * (mid + 1) <= (long) 2 * n) {
                left = mid;
            }else {
                right = mid - 1;
            }
        }
        return left;
    }
    public int arrangeCoins1(int n) {
        //暴力枚举
        int x = n;
        for(int i = 1;i <= n;i++) {
            x -= i;
            if(x < 0) {
                return i - 1;
            }
            if(x == 0) {
                return i;
            }
        }
        return -1;
    }

    //374、猜数字大小
    int guess(int num) {
        return 0;
    }
    public int guessNumber(int n) {
        int left = 1,right = n;
        while(left < right) {
            int mid = left + (right - left + 1) / 2;
            if (guess(mid) >= 0) {
                left = mid;
            }else {
                right = mid - 1;
            }
        }
        if (guess(left) == 0) {
            return left;
        }else {
            return -1;
        }
    }

    //367、有效的完全平方数
    public boolean isPerfectSquare(int num) {
        int left = 0,right = num;
        while(left < right) {
            int mid = left + (right - left) / 2;
            long sq = (long) mid * mid;
            if (sq < num) {
                left = mid + 1;
            }else {
                right = mid;
            }
        }
        long sq = (long) (left * left);
        if (sq == num) {
            return true;
        }else {
            return false;
        }
    }
}
